package main

import "fmt"

type Node struct {
	data int
	Next *Node
}
type CircleList struct {
	first *Node
}

func NewCircleList() *CircleList {
	return &CircleList{
		first: nil,
	}
}
func (a *CircleList) Add(newNode *Node) {
	if a.first == nil {
		a.first = newNode
		a.first.Next = a.first
		return
	}
	temp := a.first
	for {
		if temp.Next != a.first {
			temp = temp.Next
			continue
		}
		break
	}
	temp.Next = newNode
	newNode.Next = a.first
}
func (a *CircleList) Remove() {
	if a.first == nil {
		fmt.Println("列表为空")
		return
	}
	helper := a.first
	for ; helper.Next != a.first; helper = helper.Next {
	}
	for {
		if helper == a.first {
			break
		}
		countNum := 2
		for i := 0; i < countNum-1; i++ {
			a.first = a.first.Next
			helper = helper.Next
		}
		fmt.Println("出圈：", a.first.data)
		a.first = a.first.Next
		helper.Next = a.first
		a.PrintList()
	}
}
func (a *CircleList) PrintList() {
	if a.first == nil {
		fmt.Println("列表为空")
		return
	}
	temp := a.first
	for {
		fmt.Printf("=>%d ", temp.data)
		if temp.Next == a.first {
			break
		}
		temp = temp.Next
	}
	fmt.Printf("\n")
}

func main() {
	// 约瑟夫问题，报数出圈，1、2报数，2的出圈，最后只有一个人留下
	l := NewCircleList()
	for i := 1; i < 5; i++ {
		l.Add(&Node{data: i})
	}
	l.PrintList()
	l.Remove() //报数，出圈
}
